package seqList.LeetCode;
// LeetCode 第234题 给定一个头节点，判断链表是否是回文
public class Num234 {
    public boolean isPalindrome(ListNode head) {
        //1.查找中间节点
        ListNode middleNode = middleNode(head);
        //反转中间节点之后的链表并且保存到l2
        ListNode l2 = reverseList(middleNode);
        //l1 l2同时遍历
        while (l2 != null){
            if(head.val !=  l2.val){
                return false;
            }
            l2 = l2.next;
            head=head.next;
        }
        return true;
    }
    //中间节点的查找
    public ListNode middleNode(ListNode head){
        //fast一次两步，low一次一步
        ListNode fast = head;
        ListNode low = head;
        //终止条件 fast == null（偶数） && fast.next == null（奇数）
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            low =low.next;
        }
        //fast走完 low到中间
        return low;

    }
    //反转链表
    public ListNode reverseList(ListNode head) {
        //如果是空或者只有头节点，返回
        if(head == null || head.next == null){
            return head;
        }
        ListNode DummyHead = new ListNode(5001);
        //至少有两个节点
        while (head != null) {
            ListNode node = new ListNode(head.val);
            node.next = DummyHead.next;
            DummyHead.next = node;
            head = head.next;
        }
        return DummyHead.next;
    }

}
